package leetcode.editor.cn;

/**
 * 归并排序
 */
public class AMergeSort implements AIOrder{
    @Override
    public void sort(int[] nums) {
        if (nums == null) {
            return;
        }
        merge(nums, 0, nums.length-1);
    }

    public void merge(int[] nums, int first, int second) {
        int interval = second - first;
        if (interval < 1) {
            return;
        }

        if (interval == 1) {
            if (nums[first] > nums[second]) {
                swap(nums, first, second);
            }
        }

        int mid = first + ((second-first)>>1);
        merge(nums, first, mid);
        merge(nums, mid+1, second);
        order(nums, first, mid, second);
    }

    public void swap(int[] nums, int first, int second) {
        nums[first] ^= nums[second];
        nums[second] ^= nums[first];
        nums[first] ^= nums[second];
    }

    public void order(int[] nums, int first, int middle, int second) {
        int[] temp = new int[second-first+1];
        if (nums[middle] < nums[middle+1]) {
            return;
        }

        int index = 0, firstStart = first, secondStart = middle+1;
        while (firstStart <= middle && secondStart <= second) {
            if (nums[firstStart] < nums[secondStart]) {
                temp[index] = nums[firstStart];
                firstStart++;
            } else {
                temp[index] = nums[secondStart];
                secondStart++;
            }
            index++;
        }

        while (firstStart <= middle) {
            temp[index] = nums[firstStart];
            firstStart++;
            index++;
        }

        while (secondStart <= second) {
            temp[index] = nums[secondStart];
            secondStart++;
            index++;
        }

        for (int value : temp) {
            nums[first++] = value;
        }
    }

    public static void main(String[] args) {
        AIOrder order = new AMergeSort();
        int[] nums = new int[]{8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        order.sort(nums);
        System.out.println("end");
    }
}
